#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;
// 本次排序都是按照升序排的

void bubbleSort(vector<int> &nums)
{
    int n = nums.size();
    for (int i = 0; i < n - 1; i++)
    {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (nums[j] > nums[j + 1])
            {
                swap(nums[j], nums[j + 1]);
                swapped = true;
            }
        }
        if (!swapped)
            break;
    }
}

void SelectSort(vector<int> &nums)
{
    int n = nums.size();
    for (int i = 0; i < n - 1; i++)
    {
        int minIndex = i;
        for (int j = i + 1; j < n; j++)
        {
            if (nums[j] < nums[minIndex])
            {
                minIndex = j;
            }
        }
        swap(nums[i], nums[minIndex]);
    }
}
void InsertSort(vector<int> &nums)
{
    int n = nums.size();
    for (int i = 1; i < n; i++)
    {
        int key = nums[i], j = i - 1;
        while (j >= 0 && nums[j] > key)
        {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = key;
    }
}
void ShellSort(vector<int> &nums)
{
    int n = nums.size();
    for (int gap = n / 2; gap > 0; gap /= 2)
    {
        for (int i = gap; i < n; i++)
        {
            int key = nums[i], j = i - gap;
            while (j >= 0 && nums[j] > key)
            {
                nums[j + gap] = nums[j];
                j -= gap;
            }
            nums[j + gap] = key;
        }
    }
}
int _QuickSort(vector<int> &nums, int left, int right)
{
    int key = left;
    left++;
    while (left <= right)
    {
        while (left <= right && nums[left] < nums[key])
            left++;
        while (left <= right && nums[right] > nums[key])
            right--;
        if (left <= right)
            swap(nums[left++], nums[right--]);
    }
    swap(nums[key], nums[right]);
    return right;
}
void QuickSort(vector<int> &nums, int left, int right)
{
    if (left > right)
        return;
    int key = _QuickSort(nums, left, right);
    QuickSort(nums, left, key - 1);
    QuickSort(nums, key + 1, right);
}

void MergeSort(vector<int> &nums, int left, int right)
{
    if (left >= right) return;
    int mid = (left + right) >> 1;
    MergeSort(nums, left, mid);
    MergeSort(nums, mid + 1, right);
    vector<int> tmp(right-left+1);
    int cur1 = left, cur2 = mid + 1, i = 0;
    while (cur1 <= mid && cur2 <= right)
        tmp[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];
    while (cur1 <= mid)
        tmp[i++] = nums[cur1++];
    while (cur2 <= right)
        tmp[i++] = nums[cur2++];
    for (int i = left; i <= right; i++)
        nums[i] = tmp[i - left];
}

void AdjustDown(vector<int>& nums,int n,int parent)
{
    int child=parent*2+1;
    while(child<n)
    {
        if(child+1<n && nums[child+1]>nums[child]) child=child+1;
        if(nums[child]>nums[parent])
        {
            swap(nums[child],nums[parent]);
            parent=child;
            child=parent*2+1;
        }
        else
        {
            break;
        }
    }
}
void HeapSort(vector<int>& nums)
{
    int n=nums.size();
    //构建大根堆，从最后一个非叶子节点开始
    for(int i=(n-1-1)/2;i>=0;i--)
    {
        AdjustDown(nums,n,i);
    }
    //排序
    int end=n-1;
    while(end>=0)
    {
        swap(nums[0],nums[end]);
        AdjustDown(nums,end,0);
        end--;
    }
}
void RadixSort(std::vector<int>& nums) {
    int maxVal=*max_element(nums.begin(),nums.end());
    int maxDigits=0;
    while(maxVal)
    {
        maxVal/=10;
        maxDigits++;
    }
    vector<queue<int>> buckets(10);
    for(int i=0;i<maxDigits;i++)
    {
        for(int num : nums)
        {
            int bucketIndex=num/static_cast<int>(pow(10,i))%10;
            buckets[bucketIndex].push(num);
        }
        int index=0;
        for(auto& bucket : buckets)
        {
            while(!bucket.empty())
            {
                nums[index++]=bucket.front();
                bucket.pop();
            }
        }
    }
}
void Print(vector<int> &nums)
{
    for (int i = 0; i < nums.size(); i++)
    {
        cout << nums[i] << " ";
    }
    cout << endl;
}
int main()
{
    vector<int> nums = {5, 1, 4, 2, 8};
    // bubbleSort(nums);
    // SelectSort(nums);
    // InsertSort(nums);
    // ShellSort(nums);
    //QuickSort(nums, 0, nums.size() - 1);
    //MergeSort(nums, 0, nums.size() - 1);
    //HeapSort(nums);
    //RadixSort(nums);
    Print(nums);
    return 0;
}